package main

import "fmt"

/*

可以买卖多次！！！！

给定一个数组 prices ，其中prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
*/

//贪心算法
/*
func maxProfit(prices []int) int {
	var sum = 0
	for i:=0;i<len(prices)-1;i++{
		if prices[i+1]-prices[i]>0{
			sum += prices[i+1]-prices[i]
		}
	}
	return sum
}
*/

//动态规划 本次可交易无穷次 k=k-1=k-2 无影响
//dp[i][k][0]:今天第i天，手里没有股票，可以交易k次
//dp[i][k][1]:今天第i天，手里有股票，可以交易k次

//dp[-1][k][0]=dp[i][0][0] = 0
//dp[-1][k][1]=dp[i][0][1] = -∞
func maxProfit(prices []int) int {
	l := len(prices)
	dp := make([][2]int, l)
	//for i := 0; i < l; i++ {
	//	dp[i] = make([]int, 2)
	//}
	for i := 0; i < l; i++ {
		if i == 0 {
			dp[i][0] = 0
			dp[i][1] = -prices[i]
			continue
		}
		//dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+prices[i])
		//dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i])
		//此时k不会改变 且k为无穷 可以看成 k=k-1 不需要记录k的状态
		dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
		dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
	}
	return dp[l-1][0]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	num := []int{7, 1, 5, 3, 6, 4} //len=6
	fmt.Println(maxProfit(num))
}
